package main

import (
	"fmt"
)

type ListNode struct {
	value int
	next *ListNode
}

type LinkedList struct {
	head *ListNode
	//记录链表的长度
	length int
}

//返回链表的长度
func (l *LinkedList) list_len() int{
	return l.length
}

//在末尾追加元素 --考虑链表是否为空两种情况
func (l *LinkedList) app_item(item int){
	//创建实例
	new_node := &ListNode{value: item}

	if l.head == nil {
		l.head = new_node
	}else{
		cur := l.head
		//遍历 找到当前节点的下一个节点为空的地方，即尾节点
		for cur.next != nil {
			cur = cur.next
		}
		//找到后退出循环，然后把最后一个节点的下一个节点指向新节点
		cur.next = new_node
	}
	//添加一个元素长度加1
	l.length++
}

//在链表的头部添加元素
func (l *LinkedList) app_left(item int){
	new_node := &ListNode{value: item}

	if l.head == nil{
		l.head = new_node
	}else{
		//将新的指向原来的 头节点
		new_node.next = l.head
		l.head = new_node
	}
	l.length++
}

//遍历
func (l *LinkedList) iter_List(){
	//定义一个游标来遍历
	cur := l.head
	//当前节点不为空时
	for cur != nil{
		fmt.Printf("%d ->", cur.value)
		cur = cur.next
	}
	fmt.Println("nil")
}

//在指定位置insert元素  --分三种情况  --下标从0开始
func (l *LinkedList) insert(index int, item int){
	new_node := &ListNode{value: item}
	if index == 0{
		l.app_left(item)
	}else if index > l.length || index < 0{
		return
	}else{
		cur := l.head
		for i := 0; i < index - 1;i++{
			cur = cur.next
		}
		new_node.next = cur.next
		cur.next = new_node
	}
	l.length++
}

//删除指定节点
func (l *LinkedList) remove(item int){
	if l.head == nil{
		return
	}
	if l.head.value == item{
		l.head = l.head.next
		l.length--
	}
	pre := l.head
	cur := l.head.next
	for cur != nil{
		if cur.value == item{
			pre.next = cur.next
			l.length--
			return
		}
		pre = cur
		cur = cur.next
	}
}

//查找元素是否在链表中
func (l *LinkedList) search(item int) bool{
	cur := l.head
	for cur != nil{
		if cur.value == item{
			return true
		}else{
			cur = cur.next
		}
	}
	return false
}

//链表的反转
func (l *LinkedList) reverseList(){
	if l.head == nil || l.head.next == nil{
		return
	}
	var pre *ListNode = nil
	cur := l.head
	for cur != nil{
		next := cur.next
		cur.next = pre
		pre = cur
		cur = next
	}
	l.head = pre
	l.iter_List()
}
// 链表的排序
func (l *LinkedList)sort(list2 *LinkedList) *LinkedList{
	// 先合并
	new_List := &LinkedList{}
	new_length := 0
	cur1 := l.head
	cur2 := list2.head
	if cur1 != nil && cur2 != nil{
		for cur1.next != nil {
			cur1 = cur1.next
		}
		cur1.next = cur2
		new_List = l
		new_length = l.length + list2.length
		//fmt.Println(new_length)
		new_List.iter_List()
	}
	//排序
	if new_List.length <= 1{
		return new_List
	}
	for i := 0 ; i < new_length ; i++{
		cur := new_List.head
		for cur != nil && cur.next != nil {
			if cur.value > cur.next.value {
				cur.value, cur.next.value = cur.next.value, cur.value
			}
			cur = cur.next
		}
	}
	new_List.iter_List()
	return new_List
}

func main(){
	node1 := &LinkedList{}
	node1.app_item(100)
	node1.app_item(30)
	node1.app_item(50)
	node1.app_item(70)
	node1.iter_List()

	node2 := &LinkedList{}

	node2.app_item(20)
	node2.app_item(40)
	node2.app_item(60)

	node2.iter_List()

	node1.sort(node2)
}